package cn.edu.zufe.mjt.dp;

import java.util.Scanner;

/**
 * 动态规划 —— 爬楼梯
 *
 * 问题描述：
 * 小明正在爬楼梯。楼梯总共有n级台阶，小明每次可以选择爬1级或2级台阶。
 * 请问小明爬到第n级台阶的不同方法有多少种。
 * 注意:假设小明从地面(第0级台阶)开始爬楼梯，每次可以从当前台阶选择爬1级或2级台阶，直到到达第 n级台阶。
 *
 */
public class ClimbStairs {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long result = dp(n);
        System.out.println(result);
    }

    /**
     * 以爬楼梯为例，从两个视角拿捏动态规划问题：
     * 递归视角：需要理解递归树，假设最开始为 5 级台阶，则递归树为：
     *                       5
     *                      / \
     *                     4   3
     *                    / \ / \
     *                   3  2 2  1
     *                  / \
     *                 2  1
     *                / \
     *               1  0
     * 可以看到递归树里有重复的计算，因此可以用记忆化搜索的方式优化递归过程。
     * 假设用一个数组存储中间结果，则可以用 dp[i] 表示爬到第 i 级台阶的方法数。
     * 因此边界条件以及递归条件可以调整为：
     * function f(n):
     *     if n == 1:
     *         return 1
     *     else if n == 2:
     *         return 2
     *     else:
     *         if n in memo:
     *             return memo[n]
     *         memo[n] = f(n-1) + f(n-2)  // 这里保证了每个节点只计算一次，避免重复计算以降低复杂度
     */
    public static long dp(int n) {
        // 从递归的角度看
        // 考虑递归解法:假设站在第n级台阶，上一步可能从第n-1级台阶来，也可能从第n-2级台阶来
        //递归方程为:f(n)=f(n-1)+f(n-2)，其中f(x)为从0到x级台阶的方案数边界条件:f(0)=1,f(1)= 1
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 从数学推导的角度看动态规划
     * ① 慢就是快，枚举所有情况：还是假设 n = 5，那么列出所有的情况
     * 0->1->2->3->4->5                                     0->1->2->3->4->5
     * 0->1->3->4->5                                        0->1->3->4->5
     * 0->1->3->5       归类：定义一个集合                     0->1->2->4->5
     * 0->1->2->3->5    那么所有 n=5 的方案称之为 D(5)   ==>      0->2->3->4->5
     * 0->1->2->4->5                                        0->2->4->5
     * 0->2->3->4->5
     * 0->2->3->5                                          0->1->3->5
     * 0->2->4->5                                          0->1->2->3->5
     *                                                     0->2->3->5
     * 那么将这些情况分成两类：
     * 倒数第二个数是 4 的一类，导师第二个是 3 的一类。最后一个是5，这是毋庸置疑的。
     * 之后进行集合划分，就可以划分出 D(5,4) 和 D(5,3) 这两个集合。D(x,y) 表示留在 x 节点，并且上一步是从 y 来的。
     * 那么就有 D(5) = D(5,4) ∪ D(5,3)  于是 |D(5)| = |D(5,4)| + |D(5,3)|
     * ② 集合映射：
     * 因为 D(5,4) 都是以 5 结尾，那么去掉 最后的5之后，就得到了 D(4)，这里可以看到 D(4) 里的方案就是从 0 台阶到 4 台阶的所有方案。
     * 因此有 D(5,4) = D(4)，同理得到 D(5,3) = D(3)。所以就有了 |D5| = |D(5,4)| + |D(5,3)| = |D(4)| + |D(3)|
     * ③ 推广至普遍情况：
     * 对于任意n的方案集合 D(n),其每个元素为一个序列 path[i] ∈ D(n), 形如[S1,S2,S3,…,S]都满足Sk∈{n-1,n-2}
     * 根据Sk[i-1]的取值，将D(n)拆分成两个部分:D(n,n-1),D(n,n-2) 且满足|D(n)|= |D(n,n-1)| + |D(n,n-2)|
     * 定义f:S→S',f(path)= path[1:|path|-1]
     * D(n,n-1) = { f(path[i])|path[i] ∈ D(n,n-1) }
     * D(n,n-2) = { f(path[i])|path[i] ∈ D(n,n-2) }
     * 容易证明：|D(n,n-1)| = |D(n-1)| , |D(n,n-2)| = |D(n-2)|
     * |D(n)| = |D(n-1)| + |D(n-2)|
     * ④ 总结：
     * ①构造集合:从具体例子出发，列出所有情况 D(5)
     * ②寻找等式:根据集合元素中上一个位置的取值进行集合划分 |D(5)| = |D(5,4)| + |D(5,3)|
     * ③集合映射:去掉集合元素的最后一个元素，集合映射为子问题形式 |D(4)| 和 |D(3)|
     * ④推广得到递推式: |D(n)| = |D(n-1)| + |D(n-2)|
     * ⑤列举边界情况: |D(0)| = 1, |D(1)| = 1
     *
     */
    public static int dp2(int n) {
        return 0;
    }
}
